import re
from fractions import gcd
from random import *

class RSA:
	def __init__(self, prime_q, prime_p):
		self.p = prime_p
		self.q = prime_q

	@classmethod
	def findEncryptionKey(self,eulerPhi):
		try:
			for i in range(1,eulerPhi):
				encrypt = randint(1, eulerPhi)
				if gcd(eulerPhi, encrypt) == 1: #Greatest Common Divisor (GCD)
					return encrypt
					break
		except Exception, error:
			print "Error finding encrypt value."
			print error

	@classmethod
	def findDecryptionKey(self,eulerPhi,e):
		try:
			for decrypt in range(1,eulerPhi):
				if (e*decrypt-1) % eulerPhi == 0:
					return decrypt
					break
		except Exception, error:
			print "Error finding decrypt value."
			print error

	@classmethod
	def messageToList(self,message):
		
		if message[-1] == ' ': #verifier for first and last
			message = message[:-1]

		if len(message) % 2 != 0: #not even
			message = message+'b'

		if ' ' in message:
			message = message.replace(' ', 'b')

		listToString = ''.join(message)
		return listToString

	@classmethod
	def messageToCipher(self,blocksOfMessage):
		_encryptedBlocks = []
		for block in messageToBlocks:
			counter =0
			print "-- Block ",block,"--"
			key = block[counter]
			value = atoz[key]
			#print value
			counter+=1
			#print atoz[block[counter]]
			#print len(atoz)
			temp = (value*len(atoz))+(atoz[block[counter]]) #works only when step=2
			print "Temp is:",temp
			cipher = pow(temp,e) % n 
			print "encrypted text is:",cipher
			_encryptedBlocks.append(int(cipher))
		return _encryptedBlocks

	@classmethod
	def cipherToMessage(self, blocksOfCipher,atoz):
		_decryptedBlocks = []
		for block in blocksOfCipher:
			print "-- Block ",block,"--"
			temp = pow(block,d) % n
			first_char = temp/len(atoz) #int of first char
			second_char = temp - int(first_char) * len(atoz) #int of 2nd char
			decryptedBlock = atoz.keys()[atoz.values().index(first_char)]+atoz.keys()[atoz.values().index(second_char)]
			_decryptedBlocks.append(decryptedBlock)
		return _decryptedBlocks


if __name__ == '__main__':
	rsa = RSA(47,59)
	n = rsa.p * rsa.q # public key

	atoz = {"A": 0, "B": 1, "C": 2, "D": 3, "E": 4,
		"F": 5, "G": 6, "H": 7, "I": 8, "J": 9, "K":10,
		"L": 11, "M": 12, "N": 13, "O": 14, "P": 15, "Q": 16,
		"R": 17, "S": 18, "T": 19, "U": 20, "V": 21, "W": 22,
		"X": 23, "Y": 24, "Z": 25, "b": 26 # b is for spaces 
			}

	print "public key n =",n
	eulerPhi = (rsa.p-1)*(rsa.q-1) # eulerPhi(n) = (self.p-1, self.q-1)
	print "eulerPhi =",eulerPhi
	e = rsa.findEncryptionKey(eulerPhi)
	#e=17
	print "Public (encryption key) e =",e
	d = rsa.findDecryptionKey(eulerPhi, e)
	print "Private (decryption key) d =",d

	print """Welcome to RSA Lab
	[*] Press CapsLock to prevent errors.
	[*] Please use only A-Z and spaces. Numbers are not allowed yet.
	"""
	message = ''
	counter=4 # 5 attempts
	while counter>=0:
		try:
			message = "YES NO"#raw_input('Please send the message: ') #raw_input() is for command-line execution
			message = re.search(re.compile(r'^[A-Z\s*]+$', re.I|re.M), message)
			print "[V] Thank You. Your message is", message.group(0)
			#message = message.upper()
			counter=-1
		except:
			print "[!] An error was found in your message. It might contain unrestricted characters."
			print "You have",counter,"attempts left."
			message = ''
			counter -= 1
			if counter==0:
				print "[!] You've run out of attempts. Goodbye."
				exit(0)
	message = message.group(0)
	messageAsList = rsa.messageToList(message)

	"""Split characters to blocks"""
	step = 2 # blocks
	messageToBlocks = [messageAsList[i:i+step] for i in range(0,len(messageAsList),step)]
	print "Here is the message as blocks:",messageToBlocks

	"""encrypting the text"""
	blocksOfCipher = rsa.messageToCipher(messageToBlocks)

	print "This is the message: ",message
	#cipher = pow(message,e) % n
	print "This is the cipher:", blocksOfCipher

	print "==== Time To Decrypt ===="
	decrypted = rsa.cipherToMessage(blocksOfCipher,atoz)
	print decrypted